# 给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：
#  任何左括号 ( 必须有相应的右括号 )。
#  任何右括号 ) 必须有相应的左括号 ( 。
#  左括号 ( 必须在对应的右括号之前 )。
#  * 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
#  一个空字符串也被视为有效字符串。
#
#  示例 1:
# 输入: "()"
# 输出: True
#
#  示例 2:
# 输入: "(*)"
# 输出: True
#
#  示例 3:
# 输入: "(*))"
# 输出: True
class Solution:
    def checkValidString3(self, string: str) -> bool:
        """
        解法三:贪心
        :param string:
        :return:
        """
        maxCount, minCount = 0, 0  # 未匹配的左括号数量可能的最小值和最大值
        for char in string:
            if char == '(':
                maxCount += 1
                minCount += 1
            elif char == '*':
                minCount = max(minCount - 1, 0)  # 将'*'作为右括号或者空(看成''时要前面所有的'('都已匹配)
                maxCount += 1  # 将'*'作为'('
            else:
                minCount = max(minCount - 1, 0)
                maxCount -= 1
                if maxCount < 0:  # 说明没有左括号可以和右括号匹配，返回 false
                    return False
        return minCount == 0

    def checkValidString2(self, string: str) -> bool:
        """
        解法二:
        两个栈
        :param string:
        :return:
        """
        stack1 = []  # 用于存放 s中的 '(' 的索引
        stack2 = []  # 用于存放 s中的 '*' 的索引
        i = 0
        while i < len(string):
            if string[i] == '(':  # 遇到 '(' 时
                stack1.append(i)
            elif string[i] == '*':  # 遇到 '*' 时
                stack2.append(i)
            else:  # 遇到 ')' 时
                if stack1:  # 优先和'('进行匹配
                    stack1.pop()
                elif stack2:  # 没有了可以匹配的 '(' 则尝试与 '*' 进行匹配
                    stack2.pop()
                else:  # 当前的 ')' 不能完成匹配, 直接返回false
                    return False
            i += 1

        if len(stack1) > len(stack2):  # 有剩余的 '('未被匹配完毕，则一定不会匹配，此时将 '*' 看成 ')'
            return False

        while stack1 and stack2:  # stack1, stack2都不为空说明还有 '('和 '*'未被匹配
            # 必须保证 '(' 在 '*' 的左边才能匹配成功即 stack1的栈顶元素 < stack2的栈顶元素
            if stack2[-1] < stack1[-1]:
                return False
            stack1.pop()
            stack2.pop()
        return True

    def checkValidString1(self, string: str) -> bool:
        """
        解法一:动态规划
        dp[i][j] 表示字符串 s 从下标 i 到 j 的子串是否为有效的括号字符串
        从短的子串逐渐推算出长的子串的有效性
            首先计算所有长度为1和2的子串的有效性(边界值)
            然后计算长度大于2的子串的有效性: 需要根据子串的首尾字符以及中间的字符判断子串是否为有效的括号字符串
                有效的子串有两种情况
                    1. s[i] 和 s[j] 分别为左括号和右括号，或者为 '*' dp[i][j] 取决于 dp[i + 1][j - 1]
                    2. 如果存在 k (i <= k < j) 使得 dp[i][k] 和 dp[k+1][j] 都为 true，则 dp[i][j]=true
        :param string:
        :return:
        """
        n = len(string)
        dp = [[False for i in range(n)] for j in range(n)]  # 声明一个 n * n的矩阵(深拷贝)
        # dp = [[False for i in range(n)]] * n  # 声明一个 n * n的矩阵(浅拷贝矩阵的每一行的地址都一样)
        # print(dp)

        # 计算边界(即长度为1或者2的子串是否是有效字符串)
        i, j = 0, 0
        while i < n:  # 长度为1的只有'*'是有效子串
            if string[i] == '*':
                dp[i][i] = True
            i += 1
        i = 1
        while i < n:  # 长度为2的只有“()",“(*",“*)",“**" 中的一种情况时是有效子串
            c1, c2 = string[i - 1], string[i]
            dp[i - 1][i] = (c1 == '(' or c1 == '*') and (c2 == ')' or c2 == '*')
            i += 1

        # 子串的长度大于 2 时，需要根据子串的首尾字符以及中间的字符判断子串是否为有效的括号字符串(从短的子串逐渐推算出长的子串的有效性)
        i = n - 3
        while i >= 0:  # 控制左边界
            chi = string[i]
            j = i + 2
            while j < n:  # 控制右边界
                chj = string[j]
                # 情况1:s[i] 和 s[j] 分别为左括号和右括号，或者为 '*' dp[i][j] 取决于 dp[i + 1][j - 1]
                if (chi == '(' or chi == '*') and (chj == ')' or chj == '*'):
                    dp[i][j] = dp[i + 1][j - 1]

                # 情况2:如果存在 k (i <= k < j) 使得 dp[i][k] 和 dp[k+1][j] 都为 true，则 dp[i][j]=true
                k = i
                while k < j and not dp[i][j]:
                    dp[i][j] = dp[i][k] and dp[k + 1][j]
                    k += 1

                j += 1

            i -= 1

        return dp[0][n - 1]

    def checkValidString(self, s: str) -> bool:
        return self.checkValidString1(s)


if __name__ == "__main__":
    s = "(*))"
    # s = "((())*((*****))"
    print(Solution().checkValidString(s))
